import java.util.HashMap;
import java.util.Map;
/**
 * 146. LRU Cache LRU 缓存
 * https://leetcode.com/problems/lru-cache/description/
 */
class LRUCache {
    private static class Node{
        int key, value;
        Node prev, next;

        Node(int k, int v){
            key = k;
            value = v;
        }
    }
    private final int capacity;
    private final Node dummy = new Node(0, 0); //哨兵节点
    private final Map<Integer, Node> cache = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.prev = dummy;
        dummy.next = dummy;
    }
    
    public int get(int key) {
        Node node = getNode(key);
        return node != null? node.value : -1;
    }
    
    /**
     * 方法：从缓存中获取键对应的值，如果存在则将其移动到链表头部（最近使用）
     * 
     * Args:
     *   key: 要获取值的键
     * 
     * Returns:
     *   如果键存在则返回对应的值，否则返回-1
     * 
     * Time: O(1) - HashMap查找和链表操作都是常数时间
     * 
     * Space: O(min(p,capacity))，其中 p 为 put 的调用次数。
     */
    public void put(int key, int value) {
        Node node = getNode(key);
        if(node != null){
            node.value = value; //更新值
            return;
        }
        node = new Node(key, value);
        cache.put(key, node);
        addToHead(node); //新节点插入头部
        if(cache.size() > capacity){ //容量超出
            Node lastNode = dummy.prev;
            cache.remove(lastNode.key);
            removeNode(lastNode);
        }
    }

    // 获取 key 对应的节点，同时把该节点移到链表头部
    private Node getNode(int key){
        if(!cache.containsKey(key)){
            return null;
        }
        Node node = cache.get(key);
        removeNode(node);
        addToHead(node);
        return node;
    }

    // 删除一个节点
    private void removeNode(Node x){
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }

    // 在链表头添加一个节点
    private void addToHead(Node x){
        x.prev = dummy;
        x.next = dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */